package com.hanxiaozhang.no10leetcode.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * 〈一句话功能简述〉<br>
 * 〈给了一棵树的前序遍历和中序遍历，要求重建这棵树〉
 * 示例 1:
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 输出: [3,9,20,null,null,15,7]
 * 示例 2:
 * 输入: preorder = [-1], inorder = [-1]
 * 输出: [-1]
 * <p>
 * 思路：见方法1注释
 *
 * @author hanxinghua
 * @create 2024/4/10
 * @since 1.0.0
 */
public class No105ConstructByPreorderAndInorderTraversal {

    public static void main(String[] args) {

        int[] preOrder = {3, 9, 20, 15, 7};
        int[] inOrder = {9, 3, 15, 20, 7};

        TreeNode tree = method1(preOrder, inOrder);

        System.out.println();
    }


    /**
     * 方法1（递归方式）：
     * <p>
     * 思路：
     * 对于任意一颗树而言，前序遍历的形式：
     * [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]，即根节点总是前序遍历中的第一个节点。
     * 中序遍历的形式：
     * [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
     * 推论：
     * 1. 在中序遍历中，定位到根节点，我们就可以分别知道左子树和右子树中的节点数目。
     * 2. 由于同一颗子树的前序遍历和中序遍历的长度是相同的，因此，可以在对应的前序遍历结果中，对上述形式中的所有左右括号进行定位。
     * 这样以来，我们就知道了左子树的前序遍历和中序遍历结果  和 右子树的前序遍历和中序遍历结果，我们再递归构造出左子树和右子树，
     * 再将这两颗子树接到根节点的左右位置。
     * 细节：
     * 在中序遍历中，对根节点进行定位时，一种简单的方法是直接扫描整个中序遍历的结果并找出根节点，但这样做的时间复杂度较高。
     * 考虑空间换时间：创建哈希表 <一个元素（节点的值）,中序遍历中的出现位置> 。在构造二叉树的过程之前，遍历出中序的哈希表。
     *
     * @param preOrder
     * @param inOrder
     * @return
     */
    public static TreeNode method1(int[] preOrder, int[] inOrder) {
        int n = preOrder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        Map<Integer, Integer> inIndexMap = new HashMap<Integer, Integer>(8);
        for (int i = 0; i < n; i++) {
            inIndexMap.put(inOrder[i], i);
        }
        return recursion(preOrder, inIndexMap, 0, n - 1, 0, n - 1);
    }


    /**
     * 递归
     *
     * @param preOrder      先序遍历数组
     * @param inIndexMap    中序遍历Map
     * @param preLeftIndex  本次递归二叉树的先序遍历数组左边界位置
     * @param preRightIndex 本次递归二叉树的先序遍历数组右边界位置
     * @param inLeftIndex   本次递归二叉树的中序遍历数组左边界位置
     * @param inRightIndex  本次递归二叉树的中序遍历数组右边界位置
     * @return
     */
    public static TreeNode recursion(int[] preOrder, Map<Integer, Integer> inIndexMap, int preLeftIndex, int preRightIndex, int inLeftIndex, int inRightIndex) {

        // 极值条件
        if (preLeftIndex > preRightIndex) {
            return null;
        }

        // 前序遍历中，第一个位置就是根节点
        int preRootIndex = preLeftIndex;

        // 在中序遍历Map中，定位根节点的位置
        int inRootIndex = inIndexMap.get(preOrder[preRootIndex]);

        // 建立根节点
        TreeNode root = new TreeNode(preOrder[preRootIndex]);

        // 计算左子树中，节点的数目
        int subLeftTreeSize = inRootIndex - inLeftIndex;

        // 递归地构造左子树，并连接到根节点
        // -- 先序遍历中「 左边界 + 1 , 左边界 + subLeftTreeSize」的元素 对应 中序遍历中「左边界 , 根节点-1」的元素
        root.left = recursion(preOrder, inIndexMap, preLeftIndex + 1, preLeftIndex + subLeftTreeSize, inLeftIndex, inRootIndex - 1);

        // 递归地构造右子树，并连接到根节点
        // -- 先序遍历中「 左边界 + 1 + 左子树节点数目 , 右边界」的元素  对应  中序遍历中「根节点 + 1 到 右边界」的元素
        root.right = recursion(preOrder, inIndexMap, preLeftIndex + subLeftTreeSize + 1, preRightIndex, inRootIndex + 1, inRightIndex);

        return root;
    }


}
